package com.tucc.hello.leetcode.no1601_2000.no1738;

/**
 * @author tucc
 * @description todo
 * @package com.tucc.hello.leetcode.no1601_2000.no1738
 * @date 2021/5/19
 **/
public class Solution {

    public static void main(String[] args) {
//        Solution solution = new Solution();
//        int[] arr = new int[]{9, 2, 5, 1, 3, 11, 15};
//        solution.heapSort(arr);
//        for (int i = 0; i < arr.length; i++) {
//            System.out.println(arr[i]);
//        }
//        int[][] matrix = {{5, 2},{1, 6}};
//        int k = 2;
//        System.out.println(solution.kthLargestValue(matrix, k));
    }

    public int kthLargestValue(int[][] matrix, int k) {
        int size = 0;
        int[] minHeap = new int[k];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                int a = matrix[i][j];
                for (int m = i; m < matrix.length; m++) {
                    for (int n = j; n < matrix[m].length; n++) {
                        int b = matrix[m][n];
                        int val = a ^ b;
                        if (val == 7) {
                            System.out.println(String.format("%d %d %d %d", i, j, m, n));
                        }
                        if (size < k) {
                            minHeap[size] = val;
                            size++;
                            if (size == k) {
                                initMinHeap(minHeap);
                            }
                        } else if (minHeap[0] < val) {
                            minHeap[0] = val;
                            adjustMinHeap(minHeap, minHeap.length, 0);
                        }
                    }
                }
            }
        }
        return minHeap[0];
    }

    public void heapSort(int[] minHeap) {
        initMinHeap(minHeap);
        for (int i = 0; i < minHeap.length; i++) {
            int curMl = minHeap.length - i;
            swap(minHeap, 0, curMl - 1);
            adjustMinHeap(minHeap, curMl - 1, 0);
        }
    }

    public void initMinHeap(int[] minHeap) {
        int ml = minHeap.length;
        for (int i = ml / 2 - 1; i >= 0; i--) {
            adjustMinHeap(minHeap, ml, i);
        }
    }

    public void adjustMinHeap(int[] minHeap, int ml, int cur) {
        int li = cur * 2 + 1;
        if (li >= ml) {
            return;
        }
        int ri = li + 1;
        int mi = cur;
        if (minHeap[li] < minHeap[mi]) {
            mi = li;
        }
        if (ri < ml && minHeap[ri] < minHeap[mi]) {
            mi = ri;
        }
        if (mi != cur) {
            swap(minHeap, cur, mi);
            adjustMinHeap(minHeap, ml, li);
        }
    }

    public void swap(int[] minHeap, int a, int b) {
        int temp = minHeap[a];
        minHeap[a] = minHeap[b];
        minHeap[b] = temp;
    }
}
